(A) Field of the Invention
The invention relates to a quantum computer; that is, an array of quantum bits (called qubits). More specifically, it relates to methods for using a classical computer to generate a sequence of operations that can be used to operate a quantum computer.
(B) Description of Related Art
Henceforth, we will allude to certain references by codes. Here is a list of codes and the references they will stand for.    Ref.GWiki is http://en.wikipedia.org/wiki/Grover's_algorithm    Ref.GOrig is “Quantum Mechanics Helps in Searching for a Needle in a Haystack”, by Lov. K Grover, in Phys. Rev. Letters Vol. 79, Num. 2, pp. 325-328, published on July of 1997.    Ref.GPat is “Fast Quantum Mechanical Algorithms”, U.S. Pat. No. 6,317,766, by Lov K. Grover    Ref.TexasPat is “Quantum Circuit Design for Grover's Algorithm”, U.S. Pat. No. 7,028,275, by G. Chen, Z. Diao, M. Zubairy    Ref.GPi/3 is “A Different Kind of Quantum Search” by Lov Grover, arXiv:quant-ph/0503205    Ref.Toy “Multi-phase matching in the Grover algorithm” by F. M. Toyama, W. van Dijk, Y. Nogami, M. Tabuchi, Y. Kimura, arXiv:0801.2956    Ref.TucAfga is “An Adaptive, Fixed-Point Version of Grover's Algorithm” by R. R. Tucci, arXiv:1001.5200.    Ref.TucQuibbs2 is “Quibbs, a Code Generator for Quantum Gibbs Sampling” by R. R. Tucci, arXiv:1004.2205
This invention deals with quantum computing. A quantum computer is an array of quantum bits (qubits) together with some hardware for manipulating those qubits. Quantum computers with several hundred qubits have not been built yet. However, once they are built, it is expected that they will perform certain calculations much faster that classical computers. A quantum computer follows a sequence of elementary operations. The operations are elementary in the sense that they act on only a few qubits (usually 1, 2 or 3) at a time. Henceforth, we will sometimes refer to sequences as products and to operations as operators, instructions, steps or gates. Furthermore, we will abbreviate the phrase “sequence of elementary operations” by “SEO”. SEOs are often represented as quantum circuits. In the quantum computing literature, the term “quantum algorithm” usually means a SEO for quantum computers for performing a desired calculation. Some quantum algorithms have become standard, such as those due to Deutsch-Jozsa, Shor and Grover. One can find on the Internet many excellent expositions on quantum computing.
Henceforth, we will abbreviate the phrase “Grover's Algorithm” by GA.
The original GA (first proposed in Ref.GOrig, patented in Ref.GPat, discussed in Ref.GWiki) has turned out to be very useful in quantum computing. Many quantum algorithms rely on it. It drives a starting state towards a target state by performing a sequence of equal steps. By this we mean that each step is a rotation about the same fixed axis and by the same small angle. Because each step is by the same angle, the algorithm overshoots past the target state once it reaches it.
About 8 years after Ref.GOrig, Grover proposed in Ref.GPi/3 a “pi/3 fixed-point” algorithm which uses a recursion relation to define an infinite sequence of gradually diminishing steps that drives the starting state to the target state with absolute certainty.
Other workers have pursued what they refer to as a phase matching approach to GA. Ref.Toy is a recent contribution to that approach, and has a very complete review of previous related contributions.
In this invention, we describe what we call an Adaptive, Fixed-point, Grover's Algorithm (AFGA, like Afgha-nistan, but without the h).
Our AFGA resembles the original GA in that it applies a sequence of rotations about the same fixed axis, but it differs from the original GA in that the angle of successive rotations is different. Thus, unlike the original GA, our AFGA performs a sequence of unequal steps.
Our AFGA resembles the pi/3 GA in that it is a fixed-point algorithm that converges to the target, but it differs from the pi/3 GA in its choice of sequence of unequal steps.
Our AFGA resembles the phase-matching approach of Ref.Toy, but their algorithm uses only a finite number of distinct “phases”, whereas our AFGA uses an infinite number. Unlike AFGA, the Ref.Toy algorithm is not guaranteed to converge to the target so it is not a true fixed-point algorithm.
Many quantum algorithms require a version of GA that works even if there is a large overlap between the starting state and the target state. The original GA only works properly if that overlap is very small. AFGA and the pi/3 GA do not have this small overlap limitation. However, AFGA is significantly more efficient than the pi/3 GA.
Previous patents Ref.GPat and Ref.TexasPat are based on the original GA. The inventor Tucci believes that the present invention is an important improvement on those past patents because it is based on AFGA rather than on the original GA. As explained already, contrary to the original GA, AFGA converges with absolute certainty to the target state, and it does not require a small overlap between the starting and target states.
The inventor Tucci first published a description of this invention on Jan. 28, 2010, in Ref.TucAfga. Later, Tucci discussed an application of this invention in Ref.TucQuibbs2.